package Leetcode100Hot;

import org.junit.Test;

/*
乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。

示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何子数组的乘积都 保证 是一个 32-位 整数
 */
public class _16乘积最大子数组 {

    @Test
    public void test(){
        System.out.println(maxProduct(new int[]{-2,3,-4}));
    }

    //DP
    //WA  [-2,3,-4] 测试不通过
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1]*nums[i], nums[i]);
            if (i > 1){
                dp[i] = Math.max(dp[i-2]*nums[i -1] * nums[i], dp[i]);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    //官解：DP
    //ps: 官解可能适配的范围更短
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/maximum-product-subarray/solutions/250015/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
     */
    class Solution {
        public int maxProduct(int[] nums) {
            int length = nums.length;
            long[] maxF = new long[length];
            long[] minF = new long[length];
            for (int i = 0; i < length; i++) {
                maxF[i] = nums[i];
                minF[i] = nums[i];
            }
            for (int i = 1; i < length; ++i) {
                maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
                minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
                if (minF[i] < (-1 << 31)) {
                    minF[i] = nums[i];
                }
            }
            int ans = (int) maxF[0];
            for (int i = 1; i < length; ++i) {
                ans = Math.max(ans, (int) maxF[i]);
            }
            return ans;
        }
    }


    //DP
    //ps: 如果采用最大子序和的状态转移方程会导致错误
    // 结论：当前位置的最优解未必是由前一个位置的最优解转移得到的。
    /*
    状态转移方程
    maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
    minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
    它代表第 i 个元素结尾的乘积最大子数组的乘积 f max (i)，可以考虑把 a i  加入第 i−1 个元素结尾的乘积最大或最小的子数组的乘积中，二者加上 a i ，
    三者取大，就是第 i 个元素结尾的乘积最大子数组的乘积。第 i 个元素结尾的乘积最小子数组的乘积 f min (i) 同理。
    链接：https://leetcode.cn/problems/maximum-product-subarray/solutions/250015/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
     */
    class Solution2 {
        public int maxProduct(int[] nums) {
            int length = nums.length;
            int[] maxF = new int[length];
            int[] minF = new int[length];
            maxF[0] = nums[0];
            minF[0] = nums[0];
            for (int i = 1; i < length; ++i) {
                maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
                minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
            }
            int ans = maxF[0];
            for (int i = 1; i < length; ++i) {
                ans = Math.max(ans, maxF[i]);
            }
            return ans;
        }
    }


}
